package com.zhugang.week05;

/**
 * @program algorithms
 * @description: mySqrt
 * @author: chanzhugang
 * @create: 2022/07/04 23:12
 */
public class MySqrt {

    public static void main(String[] args) {
        MySqrt mySqrt = new MySqrt();
        int res = mySqrt.mySqrt(9);
        System.out.println(res);
    }

    /**
     * x的平方根
     *
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        //转化为：求 最后一个数k， k^2 <= x
        if (x == 0) {
            return 0;
        }
        int low = 1;
        int high = x / 2 + 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            long mid2 = (long) mid * mid;
            if (mid2 <= x) {
                // 向后探测
                long mid22 = (long) (mid + 1) * (mid + 1);
                if (mid22 > x) {
                    // 命中
                    return mid;
                } else {
                    // 伪命中
                    low = mid + 1;
                }
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}